import java.util.Arrays;
import java.util.PriorityQueue;

public class 最小体力消耗路径_dj {
    public static int[] move = {1,0,-1,0,1};
    public int minimumEffortPath(int[][] heights) {
        // 先求出 n 和 m 方便使用
        // 分析求出源点到每个点的最小距离
        int n = heights.length;
        int m = heights[0].length;
        // 源点到每个点的最短距离, 更新的时候要更新成路径的最大值
        int[][] distance = new int[n][m];
        for(int[] a : distance){
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        // 源点的距离
        distance[0][0] = 0;
        // 标记路线是否走过
        boolean[][] vis = new boolean[n][m];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        heap.add(new int[]{0,0,0});
        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int a = t[0]; // i
            int b = t[1]; // j
            int c = t[2]; // 距离也就是到每个点需要的代价
            // 剪枝, 找到该点直接返回即可
            if(a == n - 1 && b == m - 1){
                return c;
            }
            // 访问过的点不再访问
            if (vis[a][b]) {
                continue;
            }
            vis[a][b] = true;
            // 上下左右四个方向移动
            for (int i = 0; i < 4; i++) {
                int x = a + move[i];// 横坐标
                int y = b + move[i + 1];// 纵坐标
                // 先判断是否越界
                if(x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]){
                    // 更新一下该路径的最大值
                    int nc = Math.max(Math.abs(heights[a][b] - heights[x][y]),c);
                    // 如果该点小于存储的距离, 更新并丢到堆中
                    if(nc  < distance[x][y]){
                        distance[x][y] = nc;
                        heap.offer(new int[]{x,y,distance[x][y]});
                    }
                }
            }
        }
        // 都找不到就返回 -1, 理论上一定可以找到, 防止编译器报错
        return -1;
    }
}
